package com.xyj.rxhui.week00;


import com.xyj.common.ListNode;

/**
 * 递归的方式合并  两两合并
 */
@SuppressWarnings(value = "all")
public class T2 {

    public static ListNode[] initNodes(){
        // node1
        ListNode node1_0=new ListNode(1);
        ListNode node1_1=new ListNode(4);
        ListNode node1_2=new ListNode(5);
        node1_0.next=node1_1;
        node1_1.next=node1_2;

        // node2
        ListNode node2_0=new ListNode(1);
        ListNode node2_1=new ListNode(3);
        ListNode node2_2=new ListNode(4);
        node2_0.next=node2_1;
        node2_1.next=node2_2;

        // node3
        ListNode node3_0=new ListNode(2);
        ListNode node3_1=new ListNode(4);
        ListNode node3_2=new ListNode(6);
        node3_0.next=node3_1;
        node3_1.next=node3_2;

        return new ListNode[] {node1_0,node2_0,node3_0};
    }

    public static void main(String[] args) {


        ListNode[] listNodes=initNodes();
        System.out.println(new T2().mergeKLists(listNodes));
    }

    public ListNode mergeKLists(ListNode[] lists) {

        if(lists==null||lists.length==0) {
            return new ListNode();
        }
        
        return process(0,lists.length-1,lists);

    }

    public ListNode  process(int left,int right,ListNode[] lists){
        if(left>=right) {
            return mergeTwoLists(lists[left],null);
        }
        if (left+1>=right) {
            return mergeTwoLists(lists[left],lists[left+1]);
        }
        int mid=left+(right-left)/2;
        ListNode leftNode=process(left,mid,lists);
        ListNode rightNode=process(mid+1,right,lists);
        return mergeTwoLists(leftNode,rightNode);
    } 



    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null) {
            return list2;
        }
        if(list2==null) {
            return list1;
        }
        ListNode head=new ListNode(-1);
        ListNode me=head;
        while(list1!=null&&list2!=null) {
            if(list1.val>list2.val) {
                head.next=list2;
                list2=list2.next;
            }else {
                head.next=list1;
                list1=list1.next;
            }
             head=head.next;  
        }
        if(list1==null) {
            head.next=list2;
        }else {
            head.next=list1;
        }
    return me.next;
    }
}